Theoretical Aspects of Distributed Computing in Sensor Networks by Sotiris Nikoletseas & José D.P. Rolim

Author:Sotiris Nikoletseas & José D.P. Rolim
Language: eng
Format: epub
Publisher: Springer Berlin Heidelberg, Berlin, Heidelberg

* * *

Theorem 1 FACE guarantees the packet delivery.

Proof We give a sketch of proof of a variation of the FACE routing algorithm. This version of FACE is the following. We consider the current node s with the destination node d. At each step, the current node s knows the position of the destination d and has in input a reference point r which is used to decide the face traversal and the change of face. At the starting point, we take . The current node s selects the face which contains the segment , and the message starts the face traversal according to the right-hand or left-hand principle. The change of face is decided when the message crosses the segment by using an edge (by using Fig. 15.7 notations). In this case, we set and . We can note that it has been shown that we can also apply without real impact on the correctness of the algorithm or on the performances of the routing protocol. After changing face, we apply the same algorithm in order to select the next face.

If at each face traversal we find an edge which crosses , we can observe easily that the distance is strictly decreasing and then the delivery is guaranteed. Then, without loss of generality, it is enough to show that the edge is always crossed in the face traversal. This is equivalent to show that there always exists an intersection between the segment and the selected face.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.